package com.yangzhe.algorithm.c039;

import java.util.ArrayList;
import java.util.List;

// 含有嵌套的表达式求值
// 力扣上本题为会员题，所以额外提供了牛客网的测试链接
// 如果在牛客网上提交，请将函数名从calculate改为solve
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
// 测试链接 : https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4
public class Code01_BasicCalculatorIII_NewCoder {
    public static void main(String[] args) {
        Code01_BasicCalculatorIII_NewCoder code01BasicCalculatorIII = new Code01_BasicCalculatorIII_NewCoder();
        int solve = code01BasicCalculatorIII.solve("1+(1+2+3+4)*5/1");
        System.out.println(solve);
    }

    public static int where;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 返回表达式的值
     * <p>
     * <p>
     * 思路：递归
     * 一、准备四个变量
     * 1. 数字栈：存放数字，共三种情况：1. 解析的数组，2.递归方法返回的数字，3.遇到* /后计算的数字
     * 2. 符号栈：存放+-，*和/临时存放，遇到下一个数字就弹出和数字栈第一个进行计算
     * 3. where：存放当前递归方法解析到的最后一个位置，方便让父级方法知道解析到哪里了
     * 4. 局部变量cur，存放数字
     * <p>
     * 二、递归流程：i = 当前表达式解析的位置  f (i)
     * 1. 逐个i位置解析，
     * 1）遇到数字，cur = cur * 10 + cur - '0'
     * 2) 遇到符号，数字存入数字栈，符号存入符号栈
     * 3) 遇到(调用子递归方法，返回值给cur
     * 4) 遇到)或数组中止位置，计算表达式并返回
     *
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve(String s) {
        where = 0;
        char[] chars = s.toCharArray();
        return f(chars, 0);
    }


    public int f(char[] chars, int i) {
        int cur = 0;
        List<Integer> nums = new ArrayList<>();
        List<String> symbols = new ArrayList<>();
        while (i < chars.length) {
            char c = chars[i];
            if (c >= '0' && c <= '9') {
                cur = cur * 10 + (c - '0');
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                push(nums, symbols, cur, c);
                cur = 0;
            } else if (c == '(') {
                cur = f(chars, i + 1);
                i = where;
            } else if (c == ')') {
                break;
            }
            i++;
        }

        // 最后一个数字入栈，没有最后一个符号，放+号最后忽略即可
        push(nums, symbols, cur, '+');
        cur = 0;
        where = i;

        return calculate(nums, symbols);
    }

    public void push(List<Integer> nums, List<String> symbols, int cur, char symbol) {
        // 获取上一个符号
        String lastSymbol = symbols.size() == 0 ? null : symbols.get(symbols.size() - 1);

        if (lastSymbol == null || lastSymbol.equals("+") || lastSymbol.equals("-")) {
            // 如果是 + -，则直接入栈，最后再计算
            nums.add(cur);
            symbols.add(String.valueOf(symbol));
        } else {
            // 如果是 * /，则先出栈，先计算再把结果数字入栈
            int lastNum = nums.get(nums.size() - 1);
            nums.set(nums.size() - 1, calculate(lastNum, cur, lastSymbol));
            symbols.set(symbols.size() - 1, String.valueOf(symbol));
        }
    }

    /**
     * 计算加减乘除
     *
     * @param a
     * @param b
     * @param symbol
     * @return
     */
    public int calculate(int a, int b, String symbol) {
        switch (symbol) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                return a / b;
            default:
                return 0;
        }
    }

    /**
     * 计算表达式，只兼容 + 和 -
     *
     * @param nums
     * @param symbols
     * @return
     */
    public int calculate(List<Integer> nums, List<String> symbols) {
        if (nums.isEmpty()) {
            return 0;
        }

        // 获取第一个数字
        int result = nums.get(0);
        // 取完所有数字，而符号栈正好会忽略掉最后一个+
        for (int i = 1; i < nums.size(); i++) {
            // 符号从第0位置开始取
            String symbol = symbols.get(i - 1);
            // 左数和右树做计算
            result = calculate(result, nums.get(i), symbol);
        }

        return result;
    }
}
